package com.xubaohua.八大排序;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @program: 选择排序 时间复杂度O(n^2) 冒泡排序五万个数据是五秒 选择排序是一秒 可见选择排序的效率要高于冒泡排序
 * @description:
 * @author: 许宝华
 * @create: 2022-04-16 17:11
 */

/**
 * 1、选择排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。
 * 2、选择排序的基本思想是：通常上我们都是假定arr[0]为最小值，第一次从arr[0]~arr[n-1]中选取最小值，与arr[0]交换，
 *    第二次从arr[1]~arr[n-1]，与arr[1]交换，以此类推，总共需要进行n-1次交换，得到有序序列。
 */
public class SelectSort {
    public static void main(String[] args) {

//        int[] arr = new int[]{105,56,1,3};
//        int[] arr = new int[]{-1,0,1,3};
        //模拟多数据排序
        int[] arrMax = new int[50000];
        for (int i = 0; i <50000 ; i++) {
            arrMax[i] = (int)(Math.random() * 8000000);
        }

        Date date = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");
        String format = simpleDateFormat.format(date);
        System.out.println(format);
//        selectSort(arr);
        selectSort1(arrMax);

        Date date1 = new Date();
        String format1 = simpleDateFormat.format(date1);
        System.out.println(format1);
    }

    /**
     * 选择排序推导过程
     * @param arr
     */
    private static void selectSort(int[] arr){
        //假定最小数下标为0，最小数为arr[0]
        int minIndex = 0;
        int min = arr[0];

        System.out.println("排序前"+Arrays.toString(arr));

        for (int i = 0+1; i < arr.length; i++) {
            //如果数组中有比假定最小数还要小的数
            if(min>arr[i]){
                minIndex = i;
                min = arr[i];
            }
        }
        //将最小数进行交换
        if(minIndex != 0){
            arr[minIndex] = arr[0];
            arr[0] = min;
        }

        System.out.println("第一轮排序"+Arrays.toString(arr));
        /*
            第二轮：优化思路 如果当前值就是整个数组的最小值，则不用发生交换
         */
        minIndex = 1;
        min = arr[1];
        for (int i = 0+3; i < arr.length; i++) {
            //如果数组中有比假定最小数还要小的数
            if(min>arr[i]){
                minIndex = i;
                min = arr[i];
            }
        }
        //将最小数进行交换
        if(minIndex != 1){
            arr[minIndex] = arr[1];
            arr[1] = min;
        }
        System.out.println("第二轮排序"+Arrays.toString(arr));

        /*
            第三轮
         */
        minIndex = 2;
        min = arr[2];
        for (int i = 0+3; i < arr.length; i++) {
            //如果数组中有比假定最小数还要小的数
            if(min>arr[i]){
                minIndex = i;
                min = arr[i];
            }
        }
        //将最小数进行交换
        if(minIndex != 2){
            arr[minIndex] = arr[2];
            arr[2] = min;
        }
        System.out.println("第三轮排序"+Arrays.toString(arr));

    }

    /**
     * 选择排序优化
     * @param arr
     */
    private static void selectSort1(int[] arr){
//        System.out.println("排序前"+Arrays.toString(arr));

        for (int i = 0; i <arr.length-1 ; i++) {

            int minIndex = i ;
            int min = arr[i];
            for (int j = i+1; j < arr.length; j++) {
                //从小到大排序用大于 从大到小用小于
                if(min>arr[j]){
                    min = arr[j];
                    minIndex = j;
                }
            }
            if(minIndex != i){
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
//            System.out.println("第"+(i+1)+"排序"+Arrays.toString(arr));
        }

    }
}
